Monadische Erweiterungen von monadic NP

Fagin zeigt in seiner bahnbrechenden Arbeit, dass die Komplexitätsklasse NP mit der logischen Sprache 'existentielle Logik zweiter Ordnung' identifiziert werden kann. Ein einfaches und daher greifbares Fragment dieser Sprache ist monadic NP. Fagin bezeichnet monadic NP als '...training ground for attacking the problems in their full generality'. In dieser Arbeit werden zwei Arten von monadischen Erweiterungen von monadic NP untersucht. Der erste Teil beschäftigt sich mit schwachen built-in Relationen.Einebuilt-in Relation B heißt schwach, falls: monadic NP + B + polynomielles Padding neq NP.Es werden zwei neue Klassen schwacher built-in Relationen (unendlich teilbare-und verpackbare built-in Relationen) eingeführt. Hauptergebnis dieses Teils ist eine Klassifizierung aller bekannten schwachen built-in Relationen mittels dieser beiden Klassen. Im zweiten Teil dieser Arbeit werden monadische Abschlüsse von monadic NP betrachtet. Besonderes Interesse gilt dabei den positiven Abschluss erster Ordnung von monadic NP (kurz: PFO(monNP)). Hauptergebnis dieses Teils ist die Aussage, dass nicht-k-Färbbarkeit (k=>3) nicht ausdrückbar ist in PFO(monNP).